There exist hundreds of different network protocols created for supporting communication between computers and other types of electronic devices. Routing protocols are the family of network protocols that enable computer routers to communicate with each other and in turn to intelligently forward traffic between respective networks. In general, a network routing protocol performs functions which include: discovery which means identifying other routers on the network; routing management for keeping track of all possible destinations (for network messages or data packets) along with some data describing the pathway; and path determination for making dynamic decisions for where to send each network message or data packet.
Examples of routing protocols include Interior Gateway Protocol (IGP) and Exterior Gateway Protocol (EGP).
IGP is a routing protocol which is used to find network path information within an autonomous system, for example a system of corporate local area networks. The gateways (hosts with routers) use this protocol for exchanging routing information in-between. The routing information can then be used by the Internet protocol (IP) or other network protocols to specify how to route transmissions (or data packets). Known IGPs are Routing Information protocol (RIP); Interior Gateway Routing Protocol (IGRP), Open Shortest Path First (OSPF) and Intermediate System to Intermediate System (IS-IS). There is also an Enhanced IGRP (EIGRP) which supports classless IP subnets and improves the efficiency of the routing algorithms compared to IGRP.
EGP is a routing protocol which is used to find network path information between different autonomous systems. EGP is commonly used in the Internet to exchange routing table information. The Border Gateway Protocol (BGP) is an example of EGP. BGP detects modifications to routing tables and selectively communicates those changes to other routers over TCP/IP. Internet providers commonly use BGP to join their networks together.
Another way to route packets is by using Multi-Protocol Label Switching (MPLS) which uses labels attached to packets to forward them through the network. The MPLS labels are advertised between routers. The IP packets are prefixed by these labels and forwarding is done on the basis of these labels and not by a destination IP address, which means forwarding of packets is based on lookup of labels rather than a lookup of the IP addresses, hence speeding up the routing procedure. For example, if Router A wishes to send a data packet to Router E, Router A will insert a header in the data packet with a label stack that contains information about the data packet, where it came from, and where it is going. Router A will then send the data packet to Router B, Router B will send the data packet to Router C, Router C will send the data packet to Router D, and Router D will send the data packet to Router E. Each Router strips away past labels and adds new ones in order to keep forwarding the data packet to where it needs to go. Hence, within each router, the incoming label is examined and its next hop is matched with a new label. The old label is replaced with the new label for the packet's next destination, and then the freshly labeled packet is sent to the next router. Each router repeats the process until the packet reaches an egress router.
MPLS is often referred to as the Layer 2.5 in between the Data Link layer (Layer 2) and Network layer (Layer 3) of the seven-layer OSI model (Open Systems Interconnection model) because of where it operates.
There are, however, several problems with current routing protocols. For instance, they require a long list of entries in routing tables, and need to be updated whenever there are changes in the network. Label switching using MPLS achieves faster routing but MPLS needs to be run over another routing protocol for it to work. This means that two protocols need to run in parallel in each router and due to that, the required resources are doubled. Further, in MPLS, each router needs to generate a new label to replace the old label as explained above.
MPLS may also be used with Virtual Private Network (VPN) to allow several sites to interconnect transparently through a service provider's network. An MPLS VPN comprises a customer network and a service provider network. MPLS VPN service provider edge (PE) routers store customer routing information enabling the PE routers to route traffic belonging to respective customers for inter-site traffic. That traffic is delivered to the customer sites via respective customer edge (CE) routers.
In a MPLS VPN implementation, a PE router performs multiple functions. For example, the PE router isolates customer traffic if more than one customer is connected to the PE router. Each customer is, accordingly, assigned an independent routing table. The PE router shares theses routing tables with other deployed PE routers so that customer traffic can flow between customer sites via the service provider's own network or backbone.
A drawback with MPLS VPN is that it requires at least three different routing protocols to run simultaneously inside the service provider's network: (i) IGP routing protocol (e.g., EIGRP or OSPF) to provide internal routing; (ii) MPLS to support label switching used for VPN in each PE router and in each transit router of the SP (with the drawback that each PE and each transit router needs to generate a new label to replace the old one); and (iii) Internal BGP (or iBGP) to support Virtual Route Forwarding (VRF) features when there are many transit routers in-between, use extended community features to support VRF and to enable connectivity between PEs.
Considering the complexity of such MPLS VPN implementations, a continuing challenge for service providers is to efficiently manage their networks on behalf of their customers. There is therefore a need for a new solution for routing packets in a network topology that is easy to implement and to configure and that requires less consumption of resources, achieves fast routing of packets through fast decision making at each router and provides reduction in size of routing tables.